Critical embedded systems such as those found in military, industrial infrastructures, financial services infrastructures and medical devices require strict guarantees on information flow security. Security breaches can have extremely high costs in both monetary and human terms. These systems require rigorous design and testing to ensure that untrusted information never affects trusted computation or that secret information never leaks to unclassified domains. Cybersecurity is increasingly important as private and public institutions rely more and more on electronic data flow. There are many examples of security breaches, and contrary interests will continue to attempt to obtain access.
Timing channels are a form of a so-called side channel that can be used by those that seek to exploit secure systems, including those in military, industrial and financial services infrastructures. A side channel is created by a circuit element that leaks information unintentionally. Side channels can be exploited by adversaries to extract secret information or compromise the correct operation of high integrity components.
Modern embedded computing systems, including highly secure systems, increasingly rely upon embedded computing systems. Such systems often include a system-on-chip. A system-on-chip includes multiple cores, controllers or processors on integrated single microchip. The movement of information in such systems should be tightly controlled to ensure security goals. This is challenging because information can flow through timing channels, which are difficult to detect. In turn, hardware designs that are insusceptible to timing channels are difficult to provide because the designs can't be effectively tested for possible flaws that support timing channels.
Seminal work by Kemmerer [R. A. Kemmerer, “Shared resource matrix methodology: an approach to identifying storage and timing channels,” ACM Trans. Comput. Syst., pp. 256-277, 1983], described an informal shared-resource matrix to pin-point potential timing channels. Effective at higher computing abstractions, this technique becomes difficult to apply to embedded and application-specific designs.
A number of Ad-hoc approaches [M. Hu, “Reducing timing channels with fuzzy time,” in Proceedings of the 1991 IEEE Symposium on Security and Privacy, pp. 8-20, 1991], [. C. Wray, “An analysis of covert timing channels,” in Proceedings of the 1991 IEEE Symposium on Security and Privacy, pp. 2-7, 1991] focus on introducing random noise into a system to make extracting information stochastically difficult. These methods make a timing channel harder to exploit (lower signal-to-noise ratio), but fail to identify whether a channel is timing-based. In addition, previous work using GLIFT has shown that strict information flow isolation can be obtained in a shared bus [J. Oberg, et al., “Information flow isolation in I2C and USB,” in Proceedings of Design Automation Conference (DAC) 2011, pp. 254-259, 2011.], but the work provides no ability to relate information to timing.
Typical information flow tracking strategies target hardware description languages [X. Li et al, Caisson: a hardware description language for secure information flow,” in PLDI 2011, pp. 109-120, 20], [T. K. Tolstrup, Language-based Security for VHDL. PhD thesis, Informatics and Mathematical Modelling, Technical University of Denmark, D T U, 2007]. This can be effective to prevent timing channels from developing. However, these languages force a designer to rewrite code in a new language. This is especially cumbersome when already designed hardware modules need to be analyzed.
There are two general classes of information flows: explicit and implicit. Explicit information flows result from two subsystems directly communicating. For example, an explicit flow occurs when a host and device on a bus directly exchange data. Implicit information flows are much more subtle. Implicit flows generally leak information through behavior. Typical implicit information flows show up in hardware in the form of timing, where information can be extracted from the latency of operations.
For example, it is known that that side channel timing attacks can be used to extract secret encryption keys from the latencies of caches and branch predictors, for example. Cache timing attacks can obtain the secret key by observing the time for hit and miss penalties of the cache. Branch predictor timing channels are exploited in a similar manner, when information is leaked through the latency of predicted and mis-predicted branches. It has also been recognized that the shared bus in modern systems is a source of concern. A so-called bus-contention channel has been recognized as permitting covert transmission of information through the traffic on a global bus. See, e.g., W.-M. Hu, “Reducing timing channels with fuzzy time,” Proceedings of the 1991 IEEE Symposium on Security and Privacy, pp. 8-20, 1991.
Information flow tracking (IFT) is a common method used in secure systems to ensure that secrecy and/or integrity of information is tightly controlled. Given a policy specifying the desired information flows, such as one requiring that secret information should not be observable by public objects, information flow tracking helps detect whether or not flows violating this policy are present.
Hardware assisted IFT methods have been deployed to capture harmful flows of information including those through hardware specific timing channels Implicit flows resulting from these timing channels have been shown to leak secret keys in stateful elements such as caches and branch predictors. In addition, such timing flows can cause violations in real-time constraints, hindering real-time operations of a system or even rendering the critical system useless. Further, these channels are so hard to detect that they are usually identified only after operational critical security policies have been violated. IFT is a frequently used technique for enforcing information flow control (IFC). IFT associates a label with data, and monitors the propagation of this label through the system to check if sensitive data leaks to an unclassified domain or if integrity-critical components are affected by untrusted data. IFT has been deployed at various abstraction levels of a computing system, including in programming languages, compiler/OS, instruction set architecture and runtime systems. However, previous methods are all at too high a level of abstraction to capture hardware specific timing channels
To fully account for information flow security in critical systems, researchers have proposed Gate-Level Information Flow Tracking (GLIFT). See, Hu et al., “Theoretical Fundamentals of Gate Level Information Flow Tracking,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems (2011). GLIFT monitors all digital information flows by tracking individual bits through Boolean gates. At such a low level of abstraction, GLIFT is able to capture all transition activities including register to register timing. As a result, all digital information flows are made explicit, including timing channels that are inherent in the underlying hardware implementation but invisible to programmers. Previous work by some of the inventors has illustrated the employment of GLIFT for building verifiably information flow secure high-assurance systems. GLIFT has been shown to be effective in detecting timing channels in bus protocols such as I2C and USB. See, Oberg et al., “Information flow isolation in I2C and USB,” Design Automation Conference (DAC), 2011 48th ACM/EDAC/IEEE.
An execution lease architecture was developed to strictly bound the effects of untrusted programs. See, M. Tiwari, et al., “Execution leases: a hardware-supported mechanism for enforcing strong non-interference,” in MICRO 2009, MICRO 42, pp. 493-504 (2009). This architecture employs GLIFT to show provable information flow isolation between different execution contexts. Further, GLIFT has been used to build a provably information flow secure system from the ground level up. See, M. Tiwari, et al, “Crafting a usable microkernel, processor, and I/O system with strict and provable information flow security,” Proc. of the 38th annual international symposium on Computer architecture (ISCA'11), pp. 189-200 (New York, N.Y., 2011). Although GLIFT provides an effective approach for enforcing information flow security, the existing GLIFT method only targets a two-level linear security lattice and thus only considers two-level security labels, e.g., trusted < untrusted or, the dual, unclassified < confidential.
Many systems benefit from or require multi-level security (MLS). For example, data objects in military usage are typically classified into at least four security levels, namely top secret, secret, confidential and unclassified. A two-level linear security lattice simply cannot be used for modeling such a policy. In addition, many systems tend to be interested in non-linear lattices for modeling security policies.
For example, it is often desirable to have a policy which requires isolation of the highest security level (Top Secret) from several incomparable entities (e.g., Secret US and Secret UK). That is, the model specifies that Secret US and Secret UK are at the same level but represent two different objects. More specifically, Top Secret might be the label for a data encryption process which requires that Secret US and Secret UK learn nothing other than the cipher-text while it is perfectly secure for processes Secret US and Secret UK to learn information about one another. Prior applications of GLIFT can't provide more than two levels.